package leetcode.秋招.荣耀;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author ：zsy
 * @date ：Created 2021/8/21 18:30
 * @description：
 */
public class Main3 {
    private static boolean[][] line = new boolean[9][9];
    private static boolean[][] column = new boolean[9][9];
    private static boolean[][][] block = new boolean[3][3][9];
    private static boolean valid= false;
    private static List<int[]> spaces = new ArrayList<>();
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[][] board = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String substring = in.next().substring(1, 18);
            String[] strings = substring.split(",");
            for (int j = 0; j < strings.length; j++) {
                board[i][j] = Integer.parseInt(strings[j]);
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == 0) {
                    spaces.add(new int[]{i, j});
                } else {
                    int digit = board[i][j] - 1;
                    line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
        for (int[] nums : board) {
            StringBuilder builder = new StringBuilder();
            builder.append("{");
            for (int num : nums) {
                builder.append(num + ",");
            }
            builder.replace(builder.length() - 1, builder.length(), "}");
            System.out.println(builder.toString());
        }
    }

    private static void dfs(int[][] board, int pos) {
        if (pos == spaces.size()) {
            valid = true;
            return;
        }
        int[] space = spaces.get(pos);
        int i = space[0], j = space[1];
        for (int digit = 0; digit < 9 && !valid; digit++) {
            if (!line[i][digit] && !column[j][digit] && !block[i / 3][j / 3][digit]) {
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = digit + 1;
                dfs(board, pos + 1);
                line[i][digit] = column[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }
}
